\section{Previous work}

In this section, we describe how different implementations of
\commonlisp{} represent lexical environments, and whether these
implementations include a version of the protocol described in CLtL2.
For commercial implementations, we include only their documented
version of the CLtL2 protocol.  We start by presenting the details of
the CLtL2 protocol as described in the book.

\subsection{\commonlisp{} the Language, second edition}

Section 8.5 of CLtL2 describes a set of functions for obtaining
information from an environment object, for creating a new such object
by augmenting an existing one, and two more operators related to
environments that are outside the scope of this paper, i.e.,
\texttt{parse-macro} and \texttt{enclose}.

In this section, we provide an overview of that protocol, and we give
an assessment of its usefulness in the context of a language processor.

\subsubsection{Environment query}

For environment query, the protocol defines three functions.  We
describe them briefly here.

The function \texttt{variable-information} takes a symbol and an
optional environment object as arguments.  It returns three values.
The first value indicates the type of the binding (lexical variable,
special variable, symbol macro, constant variable) or \texttt{nil} if
there is no binding or definition in the environment for that symbol
The second value is a Boolean, indicating whether the binding is local
or global.  The third value is an association list containing
declarations that apply to the binding.

The function \texttt{function-information} takes a function name and
an optional environment as arguments.  Again, three values are
returned.  The first value indicates the type of the binding
(function, macro, special operator%
\footnote{The term used in the book is \emph{special form}, but the
  terminology has been improved since then}) or \texttt{nil} if there
is no binding or definition in the environment for that function name.
As before, the second value indicates whether the definition is local
or global, and the third value is an association list of declarations
that apply.

The function \texttt{declaration-information} is used in order to
query the environment for declarations that do not apply to any
particular binding in the environment.  It takes a \emph{declaration
  identifier}%
\footnote{The term used in the book is \emph{name} and the parameter
  is called \textit{decl-name}, but the terminology has changed since
  then.} 
and an optional environment as arguments.  The declaration identifier
can be the symbol \texttt{optimize}, the symbol \texttt{declaration},
or some implementation-defined declaration identifier.  It returns a
single value that contains information related to the corresponding
declaration identifier.

To begin with, it is clear that this set of functions is insufficient
to process all \commonlisp{} code, because no mechanism is described
for querying the environment for information related to \emph{blocks}
and \emph{go tags}.  Functions for this purpose are provided as
extensions by Allegro Common Lisp as described in
\refSec{sec-previous-allegro}, and by \lispworks{} as described in
\refSec{sec-previous-lispworks}.

\subsubsection{Environment augmentation}

For augmenting an environment, i.e., creating a new, augmented,
environment from an existing one, the same section describes the
function \texttt{augment-environment}.  This function has a keyword
parameter for each type of object to be added to the current lexical
environment: \texttt{:variable}, \texttt{:symbol-macro},
\texttt{:function}, \texttt{:macro}, and \texttt{:declare}.
Furthermore, each argument is a list of lexical definitions, thereby
allowing an arbitrary number of mappings to be added to an environment
in order to create an augmented environment.

\subsubsection{Assessment of the protocol}

In general, the protocol as described in the book is insufficient for
use in any but the simplest kind of language processor.  Even if query
functions are added for tags and blocks, and additional keyword
argument are added to the function \texttt{augment-environment} for
tags and blocks, we argue that the protocol would still be
insufficient.

Any non-trivial language processor would need for a function such as
\texttt{function-information} to return information about the
function, other than related declarations.  At the very least,
information such as the lambda list of the function, and information
needed for inlining, would have to be included.

The protocol could obviously be extended to allow for such
information, but such extensions would involve incompatible additions
such as more return values.  Furthermore, none of the \commonlisp{}
implementations we investigated use this protocol internally, which is
an indication that the compiler needs more information than the
protocol provides.  And none of the implementations we investigated
provide extensions that would allow the use of the protocol in
a non-trivial language processor.

\subsection{\sbcl{}}

\subsubsection{Native}

\sbcl{}%
\footnote{http://ww.sbcl.org/}
defines a structure class \texttt{lexenv}.  Instances of
this class are passed as the \texttt{\&environment} argument to macro
expanders and other functions that take lexical environment objects as
arguments.

This structure class contains several slots, and in particular:
\begin{itemize}
\item An association list of information about defined functions.
  The name of the function is used as a key.
\item An association list of information about defined variables.
  The name of the variable is used as a key.
\item An association list of information about blocks,
  The name of the block is used as a key.
\item An association list of information about \texttt{tagbody} tags.
  The name of the tag is used as a key.
\end{itemize}

\subsubsection{CLtL2}

The distribution of \sbcl{} contains a contribution that supplies some
of the funtionality described in the book CLtL2 but that was not
included in the \commonlisp{} standard.  Part of this contribution is
an implementation of the environment protocol of CLtL2.

\subsection{\ccl{}}

\subsubsection{Native}

\ccl{}%
\footnote{https://ccl.clozure.com/}
defines a class \texttt{lexical-environment} which is a
special kind of class called an \texttt{istruct}.  Classes of this
type are represented as lists of slots rather than as standard objects
as would normally be the case, probably for reasons of bootstrapping.

\subsubsection{CLtL2}

\ccl{} has implementations of the functions defined in CLtL2.  These
functions take a native lexical environment as an optional argument.

\subsection{\cmucl{}}

\subsubsection{Native}

A lexical environment is an instance of the structure class
\texttt{lexenv}.  There is a slot for each type of entry, i.e.,
\texttt{functions}, \texttt{variables}, \texttt{blocks},
\texttt{tags}, and some other slots for implementation-specific
details.  Each of the main slots contains an association list in which
the name is the key and the value contains associated information for
the name.

Access to the lexical environment is provided by the macro
\texttt{lexenv-find} and the function \texttt{lexenv-find-function}.
These operators do not take an environment object as an argument, and
instead access this object as the value of the special variable
\texttt{*lexical-environment*}.  And
\texttt{lexenv-find-function} is a wrapper for a call to
\texttt{lexenv-find} with a specific \texttt{:test} function for the
key of the association list containing functions.

\subsubsection{CLtL2}

\cmucl{} provides definitions of the functions defined in CLtL2.  The
code for these functions is defined in the package \texttt{ext}.  No
extensions are provided for tags or blocks.

\subsection{\ecl{}}

\subsubsection{Native}

The native compilation environment of \ecl{}%
\footnote{https://common-lisp.net/project/ecl/}
is represented as a single \texttt{cons} cell where the \texttt{car}
is a list of \emph{variable records} and the \texttt{cdr} is a list of
\emph{macro records}.  Information about blocks and tags is included
in the list of \emph{variable records}.  With few exceptions, a record
is a list with the name of the entity in the \texttt{car}.  Records
for blocks and tags are distinguished by having a keyword symbol
\texttt{:block} or \texttt{:tag} in the \texttt{car} of the list
representing the record.

\subsubsection{CLtL2}

Currently, \ecl{} does not offer a CLtL2-compatible interface to its
lexical environments.  Some work has been done to create such an
interface, but it is still work in progress.

\subsection{\clasp{}}

\subsubsection{Native}

The native compilation environment of \clasp{}%
\footnote{https://github.com/clasp-developers/clasp}
is currently that used in early versions of the Cleavir%
\footnote{https://github.com/s-expressionists/Cleavir}
compiler framework.  Ultimately,
\clasp{} will use \trucler{} as described in \refSec{sec-our-technique}.

\subsubsection{CLtL2}

\clasp{} provides an implementation of the CLtL2 protocol.
The code is present in the package named \texttt{clasp-cltl2}.  The
function \texttt{augment-environment} has two additional keyword
arguments, namely \texttt{tag} and \texttt{block}.  However, no
extension allows for client code to access information about blocks
and tags.

\subsection{\allegro{}}
\label{sec-previous-allegro}

\subsubsection{Support for CLtL2 protocol}

The documentation for Allegro \commonlisp{} contains a separate
document describing their protocol for environments in the spirit of
CLtL2.%
\footnote{https://franz.com/support/documentation/current/doc/environments.htm}
We summarize the differences between the \allegro{} implementation and
the CLtL2 protocol here.

\begin{itemize}
\item Information about blocks and tags have been added in the form of
  two new functions \texttt{block-information} and
  \texttt{tag-information}.
\item The function \texttt{augment-environment} accepts additional
  keywords arguments such as \texttt{:block}, \texttt{:tag}, etc. in
  order to make it possible to augment an environment with all
  relevant information that the language processor may encounter.
\item The function \texttt{augment-environment} accepts an additional
  keyword argument \texttt{:locative} that can be used by client code
  to supply additional information about the entity, for example the
  value of a constant variable. The query functions return an
  additional value which is the information supplied to
  \texttt{augment-environment}.
\item The order and the number of the return values of the query
  functions have been modified, so as to allow for the additional
  \emph{locative} value, and to have frequently used return values
  before the less frequently used.
\item Several other features have been added to the protocol in order
  to make it a complete tool for a language processor, and for the
  purpose of minimizing memory allocation.  These additional features
  are outside the scope of this paper.
\end{itemize}

\subsection{\lispworks{}}
\label{sec-previous-lispworks}

\subsubsection{Support for CLtL2 protocol}

The documentation for \lispworks{} \commonlisp{} describes the
operators that implement the CLtL2 protocol.  These operators are
available in the \texttt{hcl} package.

Like \allegro{}, \lispworks{} also provides the functionality for
blocks and tags that is missing from the CLtL2 protocol, but instead
of adding functions \texttt{block-information} and
\texttt{tag-information}, \lispworks{} provides a single additional
function named \texttt{map-environment}.  This function has a single
required parameter, namely an environment object.  It has four
keyword parameters: \textit{variable}, \textit{function},
\textit{block}, and \textit{tag}.  Each corresponding argument is a
designator for a function that can accept three arguments:
\textit{name}, \textit{kind}, and \textit{info} as follows:

\begin{itemize}
\item The function \textit{variable} is called for each local variable
  binding in the environment.  \textit{name} is the name of the
  variable, \textit{kind} is one of \texttt{:special},
  \texttt{:symbol-macro} or \texttt{:lexical}, with the same meaning
  as for the function \texttt{variable-information} in the CLtL2
  protocol.  When \textit{kind} is \texttt{:symbol-macro}, then
  \textit{info} is the expansion; otherwise, \textit{info} is
  unspecified.
\item The function \textit{function} is called for each local function
  in the environment. \textit{name} is the name of the function,
  \textit{kind} is one of \texttt{:macro} or \texttt{:function}, with
  the same meaning as for the function \texttt{function-information}
  in the CLtL2 protocol.  When \textit{kind} is \texttt{:macro}, then
  \textit{info} is the macro-expansion function; otherwise,
  \textit{info} is unspecified.
\item The function \textit{block} is called for each block in the
  environment.  \textit{name} is the name of the block, \textit{kind}
  is the keyword symbol \texttt{:block}, and \textit{info} is
  unspecified.
\item The function \textit{tag} is called for each tag in the
  environment.  \textit{name} is the name of the tag, \textit{kind}
  is the keyword symbol \texttt{:tag}, and \textit{info} is
  unspecified.
\end{itemize}

\noindent
However, when \texttt{map-environment} calls the function in the
keyword argument \textit{function} and the name of the function is of
the form \texttt{(setf} \textit{symbol}\texttt{)}, then the argument
is not the name of the function, but instead a symbol that is used
internally in \lispworks{} to name the function.  According to the
maintainer of \lispworks{}, this restriction will be removed in future
versions.

Similarly, the keyword argument \texttt{:function} of the function
\texttt{augment-environment} must be a list of symbols.  To represent
a function with a name of the form \texttt{(setf}
\textit{symbol}\texttt{)}, the internal symbol used by \lispworks{}
must be passed, rather than the true name of the function.  Again,
this restriction will be removed in future versions.

\subsection{CLtL2 compatibility system}

The system \texttt{cl-environments}%
\footnote{https://github.com/alex-gutev/cl-environments}
provides a compatibility layer that allows client code to use the
CLtL2 environment protocol independently of the \commonlisp{}
implementation.  Supported \commonlisp{} implementations are \clisp{},
\ccl{}, \ecl{}, \abcl{}, \cmucl{}, \sbcl{}, \allegro{}, and
\lispworks{}.

This library does not provide additional operators for querying the
environment for tags or blocks, nor does it provide keyword arguments
on \texttt{augment-environment} for augmenting an environment with
such information.

\subsection{Software including a code walker}

In his paper presented at the European Lisp Symposium 2017
\cite{raskin_mikhail_2017_3254669}, Raskin gives an overview of
various libraries that require code walking.  In that paper, he also
argues that it is impossible to write a completely portable code
walker, although he addresses many of the difficulties in his own,
mostly portable, code walker named Agnostic Lizard.

In particular, one of the libraries he mentions in his paper is
hu.dwim.walker.  This library provides a general-purpose configurable
code walker.  It uses its own protocol for accessing and augmenting
the environment.  This protocol resembles the one presented in this
paper in some ways.
